NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/8215

Internet Message Format | 1996-08-05 | 3.6 KB

Path: stc06.ctd.ornl.gov!msr!kennel
From: [e-mail] (Matt Kennel)
Newsgroups: comp.lang.c++,
Subject: Re: Tough FACTORIAL math problem...
Followup-To: comp.lang.c++,
Date: 15 Feb 1996 19:58:43 GMT
Organization: Oak Ridge National Lab, Oak Ridge, TN
Message-ID: <4g039j$[e-mail]>
References: <4fr8be$[e-mail]> <[e-mail]> <4fvp9v$[e-mail]>
NNTP-Posting-Host: msr.epm.ornl.gov
X-Newsreader: TIN [version 1.2 PL2]

G. Patrick Sand ([e-mail]) wrote:
> In article <[e-mail]>, [e-mail] says...
> >
> >The Crow wrote:
> >>
> >> Here is what I am trying to do, I want to find the last NON-ZERO digit
> > of a
> >> given factorial.  For instance,
> >>
> >> 5! = 120
> >>
> >> so the last non-zero digit is 2.  I want to be able to do this up to 1
> >000.
> [SNIP!!!]

> Here are two other approaches, which should take up very little space and
> be lightning quick:

> Since you only care about the smallest non-zero digit, just multiply the
> last smallest non-zero digit by the next number's smallest non-zero
> digit!
> You can easily test for the result being a multiple of 10.  This requires
> a bit of bookkeeping for dealing with numbers like 10, 100,
> 200, 350, etc. but that's fairly easy to handle...Heck, you could write
> three nested for(...) loops to handle going from 1-1000, although some
> purists will balk...

> If you want to minimize the testing for zero-digits, build yourself a 9x9
> matrix which holds the least-significant digit of the product of
> (i+1)*(j+1)
> [i,j are C/C++ indexes ranging from 0-8].  You then can use three nested
> for(...) loops and just select the row (new number lsd) and column (lsd
> of previous factorial) and look it up...

> The nice thing with the second approach is that it can be easily modified
> to do this in MOD J, where J is not 10.  Just adjust the for(...) loops
> to range between 0 and J-1 and have the matrix be (J-1)x(J-1) big...You
> just pay for the looping and lookup time, but you don't have to multiply
> things and divide...

I don't know if this is the *fastest* way, but it looks like it
should work and it's easy to understand.

1000! = 1000 * 999 * 998 * 997 ... *3 * 2 * 1

For each factor, f_i, express as 2^m_i * 5^n_i * p_i .

where p_i is divisible by neither 2 nor 5.

Now, out front, collect as many factors of 2*5 (i.e. 10) you can.

1000! = (10)^N * 2^m * 5^n * p_1000 * p_999 * p_998 ... *p_3 * p_2 * p_1

One or both of m or n will be zero .

Take off 10^N and multiply the remaining terms using arithmetic modulo 10.

By keeping a running loop you should be able to do this in O(1) space and
O(n) time for n!.   Through the loop, take out as many factors of 2 and
5 you can, and save that number.  Multiply the remaining factors modulo 10.
When you're done with those, see how many 2's and 5's you have left.
Make as many 10's as you can with them, discard them, and multiply the
running number by either the remaining 2's or the remaining 5's, again modulo
10.  The final answer should be "the last nonzero digit of n!".

tell me if I'm wrong.

I still feel like there's some elementary number theory that I'm missing
like

N mod p1*p2 = ??? mod p1 * ??? mod p2?

that would simplify things more

cheers
Matt

> Hope this helps...
> --
> G. Patrick Sand
> [e-mail]
> [e-mail]
> [phone]
> "Travel Light But Right..."
> Microsoft Network is prohibited from redistributing
> this work in any form, in whole or in part.   License
> to distribute this individual post is available to Microsoft
> for $999. Posting without permission constitutes an
> agreement to these terms...gps